You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

給定一個陣列，陣列中有K個linked list，每一個linked list都以升冪排列，請將這個陣列中的所有linked list合併成一個排序的linked list後回傳。

為了練習K-Way Merge，最後找到這題，想要利用這題練習一下K-Way Merge的技巧，不料點進去才發現這題的難度是Hard，從來沒練過難度Hard的題目啊啊啊!
本來想打退堂鼓，後來還是保持著嘗試的心情試著解解看。

閱讀完題目後，發現題目不難理解外，也很快就可以想到可以如何利用K-Way Merge的技巧進行解題，這一題完全是為了K-Way Merge量身訂做的呀!

廢話不多說，我們趕快進入正題吧!

先來回憶前天的K-Way Merge，主要概念就是把所有要合併的陣列，先分成兩兩一組，每組進行合併排列後，再把所有以合併的陣列，兩兩一組進行合併，如此反覆步驟，直到所有陣列都合併成一個陣列，這就是K-Way Merge的精隨。

講到這邊，就會發現這樣的做法跟題目的要求幾乎是相同的，只是陣列中換成了linked list，不過概念是相通的，只需要把合併陣列這個步驟，替換成操作Linked list合併就可以了。

解題概念

1. 參考題目提供的Example 2，先針對edge cases進行檢查，假設陣列裡面為空，則回傳null。

2. for loop每次把陣列中的lists[0]跟lists[i]的linked list進行合併。因為每一個合併後，會把合併完成的Linked list放進lists[0]的位置，所以在下一次迴圈中，會再把lists[i]再與lists[0]進行合併，直到所有合併完成，回傳lists[0]。如下圖:
   

3. 合併的步驟，先從兩個linked list的第一個節點開始進行比較，較小值者則放進要回傳的結果linked list head中，直到兩個要合併的linked list都跑完。

來點code吧!

var mergeKLists = function(lists) {
    if (!lists.length) return null;
    for (i = 1; i < lists.length; i++){
        lists[0] = merge(lists[0], lists[i]);
    }
    return lists[0];
};
var merge = function (list1, list2){
        const head = new ListNode(0); // declare a new linked list
        let currNode = head; 
        while (list1 !== null && list2 !== null) {
            if (list1.val < list2.val){
                currNode.next = list1; // put current node of list1 into result linked list
                list1 = list1.next; // move to the next node
            } else {
                currNode.next = list2;
                list2 = list2.next; 
            }
            currNode = currNode.next;
        }
        currNode.next = list1 || list2; // if only list1 or list2 is not null, just put it in currNode
        return head.next;
};